package pers.qianyu.month_202012.date_20201204.LRU;


import java.util.*;

/**
 * LRU 结构具体实现
 *
 * @author mizzle rain
 * @date 2020年12月4日16:59:08
 */
public class Cache<K, V> {
    private Node<K, V> head;
    private Node<K, V> tail;
    private final int capacity;
    private int size;
    private final HashMap<K, Node<K, V>> keyNodeMap;

    public Cache(int capacity) {
        this.capacity = capacity;
        this.keyNodeMap = new HashMap<>();
    }

    public void add(K key, V value) {
        if (this.keyNodeMap.containsKey(key)) {
            // 如果key已经存在
            Node<K, V> node = this.keyNodeMap.get(key);
            node.value = value;
            get(key);
            return;
        }
        Node<K, V> node = new Node<>(key, value);
        keyNodeMap.put(key, node);
        if (this.head == null) {
            this.head = node;
            this.tail = node;
            size++;
            return;
        }
        this.tail.next = node;
        node.pre = this.tail;
        this.tail = node;
        size++;
        if (size > capacity) {
            remove();
        }
    }

    public V get(K key) {
        Node<K, V> node = this.keyNodeMap.get(key);
        if (node == null) {
            return null;
        }
        Node<K, V> pre = node.pre;
        Node<K, V> next = node.next;
        if (pre == null) {
            // 是头结点
            this.head = head.next;
            this.head.pre = null;
            node.next = null;
            node.pre = this.tail;
            this.tail.next = node;
            this.tail = node;
            return node.value;
        }
        if (next == null) {
            // 是尾结点，直接返回
            return node.value;
        }
        // 是中间结点
        node.pre = this.tail;
        node.next = null;
        pre.next = next;
        next.pre = pre;
        this.tail = node;
        return node.value;
    }

    private void remove() {
        Node<K, V> node = this.head;
        this.head = node.next;
        this.head.pre = null;
        node.next = null;
        this.keyNodeMap.remove(node.key);
        this.size--;
    }

    public void printNodeList() {
        StringBuilder result = new StringBuilder();
        Node<K, V> h = this.head;
        while (h != null) {
            result.append(String.format("<=>{key:%s value:%s}", h.key, h.value));
            h = h.next;
        }
        System.out.println(result);
    }
}
